#ifndef __DICCTRIE__H__
#define __DICCTRIE__H__

#include <string>
#include "Tipos.h"

/**
 * Convierte un caracter a un natural.
 */
#define ord(c) ((Nat)((unsigned char)(c)))

/**
 * Implementación de DiccTrie.
 *
 * Es la implementación de un diccionario utilizando un trie.
 *
 * @remark Las claves del diccionario son siempre strings.
 * @remark No posee iteradores.
 * @remark No se pueden borrar significados.
 * @remark Se puede definir una función destructora para destruir significados en
 *         determinados momentos y así no perder memoria (Ver @link DiccTrie::EstablecerDestructor EstablecerDestructor)
 */
template<typename T>
class DiccTrie {
	public:
		/**
		 * Crea un diccionario vacío
		 * 
		 * @remark @b Complejidad: \f$\Theta(1)\f$
		 */
		DiccTrie() {
			mRaiz = NULL;
			mDestructor = NULL;
		}

		/**
		 * Destruye un diccionario.
		 *
		 * @remark @b Complejidad @f$\Theta(\#postfijos \cdot (|postfijo| + destructor))@f$, donde @b #postfijos es la cantidad
		 *         de postfijos que posee la raiz, @b |postfijo| está acotado por el postfijo más largo y @b destructor es la
		 *         complejidad del destructor establecido por el usuario para destruir un elemento.
		 */
		~DiccTrie() {
			if ( mRaiz != NULL )
				destruirNodo( mRaiz );
		}


		/**
		 * Crea o reemplaza una definición en el diccionario.
		 *
		 * @param[in] clave La clave con la cual asociar el significado.
		 * @param[in] significado El significado.
		 * @remark @b Complejidad: @f$\Theta(|clave| + copiar(significado) + destruir)@f$,
		 *         donde @b copiar(significado) es el costo de copiar el signifcado y
		 *         @b destruir es el costo de destruir el significado viejo, si es que existe
		 *         y si es que hay un destructor definido por el usuario.
		 */
		void Definir( const String &clave, const T &significado ) {
			Nat i, len;
			Nodo *p, *padre;

			if ( mRaiz == NULL )
				mRaiz = new Nodo();

			p = padre = mRaiz;
			len = clave.length();

			i = 0;
			while ( i < len ) {
				p = padre->siguientes[ ord(clave[i]) ];
				if ( p == NULL ) {
					p = new Nodo();
					padre->siguientes[ ord(clave[i]) ] = p;
				}
				padre = p;
				i++;
			}

			if ( p->definido ) {
				if ( mDestructor ) mDestructor( *(p->dato) );
				delete p->dato;
			}

			p->definido = true;
			p->dato = new T( significado );
		}

		/**
		 * Comprueba que esté definida una clave
		 *
		 * @param[in] clave La clave de la cual se desea saber su existencia.
		 * @returns @b true si la @b clave está definida en el diccionario, @b false si no lo está.
		 * @remark @b Complejidad: \f$\Theta(|clave|)\f$
		 */
		bool Definido( const String &clave ) const {
			const Nodo *p = obtenerNodo( mRaiz, clave );
			return (p != NULL) && p->definido;
		}

		/**
		 * Obtiene el significado asociado a una clave.
		 *
		 * @pre La @b clave debe estar definida en el diccionario.
		 * @param[in] clave La clave de la cual obtener su significado.
		 * @returns El significado asociado con la clave.
		 * @remark @b Complejidad: \f$\Theta(|clave|)\f$
		 * @remark @b Alias: Devuelve una referencia constante al significado.
		 */
		const T &Obtener( const String &clave ) const {
			Nodo *p = obtenerNodo( mRaiz, clave );
			return *(p->dato);
		}

		/**
		 * Obtiene el significado asociado a una clave.
		 *
		 * @pre La @b clave debe estar definida en el diccionario.
		 * @param[in] clave La clave de la cual obtener su significado.
		 * @returns El significado asociado con la clave.
		 * @remark @b Complejidad: \f$\Theta(|clave|)\f$
		 * @remark @b Alias: Devuelve una referencia modificable al significado.
		 */
		T &Obtener( const String &clave ) {
			Nodo *p = obtenerNodo( mRaiz, clave );
			return *(p->dato);
		}

		/**
		 * Define una función de destrucción de nodos.
		 * La función que se establece como destructor será llamada para destruir los elementos
		 * definidos en el diccionario en los siguientes casos:
		 * @li Durante la destrucción del diccionario, en el momento en que se destruye el nodo
		 *     que contiene al elemento.
		 * @li Cuando se define un significado para una clave previamente definida, se llamará la
		 *     función pasándole el viejo significado como parámetro.
		 *
		 * @param[in] des Puntero a una función que toma un argumento de tipo "referencia al tipo de dato
		 *            del significado".
		 * @remark @b Complejidad: @f$\Theta(1)@f$
		 */
		void EstablecerDestructor( void (*des) (T&) ) {
			mDestructor = des;
		}
		
	private:
		/**
		 * Un nodo del trie.
		 */
		struct Nodo {
			/** Constructor por defecto.
			  * @remark @b Complejidad: @f$\Theta(1)@f$
			  */
			Nodo() {
				definido = false;
				dato = NULL;
				for ( int i = 0; i < 256; i++ ) siguientes[i] = NULL;
			}

			bool definido; /**< Indica si "dato" es válido. */
			T *dato; /**< El dato almacenado en el nodo. @remark Sólo es válido si definido es @b true. */
			Nodo *siguientes[256]; /**< Puntero a 256 postfijos diferentes (uno para cada caracter). */
		};

		/**
		 * Obtiene un nodo del trie.
		 *
		 * Dada una clave y un nodo desde el cual empezar, obtiene el nodo en
		 * el que finaliza la clave.
		 *
		 * @param[in] p Puntero al nodo desde el cual empezar.
		 * @param[in] clave La clave a utilizar para la búsqueda.
		 * @returns El puntero al nodo.
		 * @remark @b Complejidad: \f$\Theta(|clave|)\f$
		 */
		Nodo *obtenerNodo( Nodo *p, const String &clave ) const {
			Nat i = 0;
			Nat len = clave.length();

			while ( i < len ) {
				if ( p == NULL ) {
					i = len;
				} else {
					p = p->siguientes[ ord( clave[i] ) ];
					i++;
				}
			}

			return p;
		}


		/**
		 * Destruye un nodo y sus postfijos.
		 * @param[in] n El nodo a destruir.
		 * @remark @b Complejidad @f$\Theta(\#postfijos \cdot (|postfijo| + destructor))@f$, donde @b #postfijos es la cantidad
		 *         de postfijos que posee, @b |postfijo| está acotado por el postfijo más largo y @b destructor es la
		 *         complejidad del destructor establecido por el usuario para destruir un elemento.
		 */
		void destruirNodo( Nodo *n ) {
			for ( int i = 0; i < 256; i++ ) {
				if ( n->siguientes[i] != NULL )
					destruirNodo( n->siguientes[i] );
			}

			if ( n->definido && mDestructor != NULL )
				mDestructor( *(n->dato) );

			if ( n->definido )
				delete n->dato;

			delete n;
		}

		Nodo *mRaiz; /**< El primer nodo, hace referencia a la cadena vacía. */
		void (*mDestructor) ( T & ); /**< La función destructora de elementos definidos. */
};

#endif
